package pers.vic.basics.datastructure.linked;

import com.sun.javafx.scene.control.skin.NestedTableColumnHeader;
import com.sun.xml.internal.ws.api.pipe.NextAction;

import java.sql.DatabaseMetaData;
import java.util.Objects;

/**
 * @author Vic.xu
 * @description: 单向链表
 * @date: 2020/10/16 0016 16:29
 */
public class SingleLinkedList implements LinkedInterface {

    /*
      Single-Linked List 单向链表：
      节点(Node)分为两个部分，
      第一个部分(data)保存或者显示关于节点的信息，
      另一个部分存储下一个节点的地址。
      最后一个节点存储地址的部分指向空值。
    */


    public SingleLinkedList() {
        this.size = 0;
        this.head = null;
    }

    /**
     * 节点的长度
     */
    private int size;

    /**头节点*/
    private Node head;

    @Override
    public Object addHead(Object obj) {
        Node newHead = new Node(obj);
        newHead.next = head;
        this.head = newHead;
        size++;
        return obj;
    }

    @Override
    public Object addTail(Object obj) {
        Node cur = head;

        if(cur == null){
            this.head = new Node(obj);
            size++;
            return obj;
        }
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = new Node(obj);
        size++;
        return obj;
    }

    @Override
    public Object deleteHead() {
        if (size <= 0) {
            throw new IllegalStateException("链表为空");
        }
        Object obj = head.data;
        head = head.next;
        size--;
        return obj;
    }

    @Override
    public Node find(Object obj) {
        Node cur = head;
        while (cur != null) {
            if (Objects.equals(cur.data, obj)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public boolean delete(Object obj) {
        if (size == 0) {
            return false;
        }
        boolean find = false;
        Node cur = head;
        //上一个节点
        Node previous = null;
        while (cur != null) {
            if (Objects.equals(cur.data, obj)) {
                find = true;
                break;
            }
            cur = cur.next;
            previous = cur;
        }
        //没有找到节点
        if (!find) {
            return false;
        }
        //当前节点为根节点，则把下个节点置为根节点
        if (cur == head) {
            head = cur.next;
        } else {
            //把当前节点的下个节挂到当前节点的上个节点之后
            previous.next = cur.next;
        }
        size--;
        return true;
    }

    public Object getHeadData() {
        if (head != null) {
            return head.data;
        }
        return null;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void display() {
        if (size == 0) {
            System.out.println(" - ");
            return;
        }
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + "->");
            cur = cur.next;
        }
        System.out.println();
    }

    @Override
    public int size() {
        return size;
    }
}
